package exchangesort;

import com.sun.xml.internal.ws.api.message.saaj.SaajStaxWriter;

import java.util.Stack;

public class Quick {

    /**
     *  时间复杂度：
     *      最好的情况下：O(N*logN)
     *      最坏情况下：O(N^2) 逆序/有序
     *  空间复杂度：
     *      最好的情况下：O(logN)
     *      最坏情况下：O(N) 逆序/有序
     *  稳定性：不稳
     * @param arr
     */
    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if(start >= end) {
            return;
        }

        int  pivot = partition(arr, start, end);
        // 左子树
        quickSort(arr,start,pivot-1);
        // 右子树
        quickSort(arr,pivot + 1,end);
    }


    /**
     *  思考2个问题：
     *    1. array[right] >= tmp 等于号
     *    2. 为什么从右边开始而不是从左边开始
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partitionHoare(int[] arr, int left, int right) {
        int temp = arr[left];
        int index = left;
        while (left < right) {
            // left < right ： 单独的循环 不能减到超过边界
            while (left < right && arr[right] >= temp) {
                right--;
            }

            while (left <right && arr[left] <= temp) {
                left++;
            }

            swap(arr, left, right);
        }
        swap(arr, index, left);
        return left;

    }
    // 挖坑法
    private int partitionHole(int[] arr, int left, int right) {
       int temp  = arr[left];
       while (left < right) {
           while (left < right && arr[right] >= temp) {
               right--;
           }
           arr[left] = arr[right];
           while (left < right && arr[left] <= temp) {
               left++;
           }
           arr[right] = arr[left];
       }
       arr[left] = temp;
       return left;
    }

    /**
     *  前后指针法
     *    总结：
     *      1. Hoare
     *      2. 挖坑法
     *      3. 前后指针法
     *    这3种方式  每次划分之后的前后顺序 有可能是不一样的
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] arr, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (arr[cur] < arr[left] && arr[++prev] != arr[cur]) {
                swap(arr, prev, cur);
            }
            cur++;
        }
        swap(arr,prev,left);
        return prev;
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

    }

    // 非递归实现快速排序
    public void sortNor(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partitionHole(arr,start, end);
        if (pivot - 1 > start) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < end) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
             end = stack.pop();
             start = stack.pop();
            pivot = partition(arr, start, end);
            if (pivot - 1 > start) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if (pivot + 1 < end) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }
}
